//#define _CRT_SECURE_NO_WARNINGS 1
//#include<iostream>
//#include<string>
//#include<vector>
//#include<algorithm>
//
//using namespace std;
//
//class message
//{
//public:
//    message(string s, int p)
//    {
//        msg = s;
//        pri = p;
//    }
//    string msg;
//    int pri;
//};
//
//message dummy(" ", -1);
//vector<message> a(100008, dummy);
//
//int main()
//{
//    int n;
//    cin >> n;
//    while (n--)
//    {
//        string input;
//        cin >> input;
//        if (input == "PUT")
//        {
//            string msg;
//            int pri;
//            cin >> msg >> pri;
//            message tmp(msg, pri);
//            a[tmp.pri] = tmp;
//        }
//        else if (input == "GET")
//        {
//            int i = 0;
//            while (a[i].pri == -1)
//            {
//                ++i;
//            }
//            cout << a[i].msg << endl;
//            a[i] = dummy;
//        }
//    }
//
//    return 0;
//}